/**
 * Created with IntelliJ IDEA.
 *
 * @Auther: 邹陆川
 * @Date: 2022/04/19/12:48 下午
 * @Description:希尔排序
 * 核心思想：
 * 分组比较，定义一个增长量来分组,
 * 外层循环，从当前h开始，i++，
 * 内层循环，从i处开始 j-=h；
 * 步长每次减半
 *
 * 时间复杂度：O = (nlogN)
 */
public class ShellSort {
  static void sort(Integer[] arr){
    //定义增长量初始值为1
    int h = 1;
    while (h<arr.length/2){
      h = h*2+1;
    }
    //定义临时变量
    int temp;
    //遍历
    while(h>=1){
      //外层循环
      for (int i = h; i < arr.length; i++) {
        //内层循环
        for (int j = i; j >= h ; j-=h) {
          if(arr[j] < arr[j-h]){
            //交换
            temp = arr[j-h];
            arr[j-h] = arr[j];
            arr[j] = temp;
          }else{break;}
        }
      }
      //增长量减半
      h = h/2;
    }
  }
}
